// 递归搜索与回溯 - 决策树问题
// 当一个题目可以使用决策树画出来，那么也可以通过递归的方法解决
// 画决策树，要保证不重不漏
// 使用全局变量进行统计，避免递归函数头传参问题
// 设计递归函数头，是否需要记录本次决策的位置，层数，个数等信息
// 回溯时注意本层计算完成后，直接在本层回溯，返回上一个位置
// 经典题目：全排列，子集

// 例题 2：
// 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
//
//        示例 1：
//
//        输入：nums = [1,1,2]
//        输出：
//        [[1,1,2],
//        [1,2,1],
//        [2,1,1]]
//        示例 2：
//
//        输入：nums = [1,2,3]
//        输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
//
//
//        提示：
//
//        1 <= nums.length <= 8
//        -10 <= nums[i] <= 10

// 解题思路：
// 关键是剪枝：
// 同一个数只能使用一次，在这个条件下：
// 第一个数不用剪枝
// 后面的数字如果不同，不用剪枝
// 后面的数字如果相同，但是不在同一层，不用剪枝

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PermuteUnique {
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] check;
    int n = 0;
    public List<List<Integer>> permuteUnique(int[] nums) {
        n = nums.length;
        check = new boolean[n];
        // 排序
        Arrays.sort(nums);
        dfs(nums);
        return ret;
    }
    public void dfs(int[] nums){
        if(path.size() == n){
            ret.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0; i < n; i++){
            if((i == 0 || (i > 0 && (nums[i] != nums[i - 1] || check[i - 1] == true))) && check[i] == false){
                path.add(nums[i]);
                check[i] = true;
                dfs(nums);
                path.remove(path.size() - 1);
                check[i] = false;
            }
        }
    }
}
